package com.example.demo.Calss16_graph;

import java.util.*;

/**
 * @program: java_base
 * @description: 利用入度 对图进行拓扑排序
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/02 13:52
 */
public class Code03_TopologySortDemo {


    // directed graph and no loop
    public static List<Node> sortedTopology(Graph graph) {
        if (graph == null || graph.nodes.isEmpty()) {
            return null;
        }
        // 节点剩余入度数
        HashMap<Node, Integer> inMap = new HashMap<>();
        // 入度为0 的入队
        Queue<Node> zeroInQueue = new LinkedList();
        for (Node node : graph.nodes.values()) {
            inMap.put(node, node.in);
            if (node.in == 0) {
                zeroInQueue.add(node);
            }
        }

        List<Node> listSort = new ArrayList<>();

        while (!zeroInQueue.isEmpty()){
            Node cur = zeroInQueue.poll();
            listSort.add(cur);
            System.out.println(cur.value);
            for (Node next :cur.nexts){
                inMap.put(next, next.in - 1);
                if (next.in == 0 ){
                    zeroInQueue.add(next);
                }
            }
        }
        return listSort;
    }

    /**
     * 遍历思路：
     *  利用队列先入先出和入度为0特性
     *  入度为0的进入队列，
     *  记录没每次遍历到
     *
     */

}
